class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        begin = 0
        end = len(nums)-1    
        if nums[0]>nums[-1]:
            # find peak
            while begin<end:
                mid = (begin+end)//2
                if nums[mid]>nums[-1]:
                    if nums[mid]<nums[mid+1]:
                        begin=mid+1
                    else:
                        begin=mid
                        break
                else:
                    end=mid-1
            peak = begin
            if target>=nums[0]:
                begin = 0
                end = peak
            else:
                begin = peak+1
                end = len(nums)-1
        while begin<end:
            mid=(begin+end)//2
            if nums[mid]>target:
                end=mid-1
            elif nums[mid]<target:
                begin=mid+1
            else:
                return mid
        return begin if nums[begin]==target else -1

print(Solution().search([2,1], 2))